{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "494241bb",
   "metadata": {},
   "source": [
    "### 不同字串"
   ]
  },
  {
   "cell_type": "raw",
   "id": "1846970f",
   "metadata": {},
   "source": [
    "一个字符串的非空子串是指字符串中长度至少为1\n",
    "的连续的一段字符组成的串。例如，字符串aaab\n",
    "有非空子串a, b, aa, ab, aaa, aab, aaab，一共\n",
    "7个。 注意在计算时，只算本质不同的串的个数。\n",
    "\n",
    "请问，字符串0100110001010001\n",
    "有多少个不同的非空子串？\n",
    "\n",
    "这是一道结果填空的题，你只需要算出结果后提交即可。\n",
    "本题的结果为一 个整数，在提交答案时只填写这个整数，\n",
    "填写多余的内容将无法得分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d2b5a79",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "string = '0100110001010001'\n",
    "\n",
    "length = len(string)\n",
    "\n",
    "strs = list()\n",
    "\n",
    "for i in range(1, length+1):\n",
    "    strs.append(string[:i])\n",
    "    \n",
    "for i in range(1 ,length+1):\n",
    "    strs.append(string[::-1][:i][::-1])\n",
    "    \n",
    "print(len(set(strs)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae3032ce",
   "metadata": {},
   "source": [
    "### 年号字串"
   ]
  },
  {
   "cell_type": "raw",
   "id": "8ad40d90",
   "metadata": {},
   "source": [
    "小明用字母A 对应数字1，B 对应2，以此类推，用Z 对应26。对于27\n",
    "以上的数字，小明用两位或更长位的字符串来对应，例如AA 对应27，AB 对\n",
    "应28，AZ 对应52，LQ 对应329。\n",
    "请问2019 对应的字符串是什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dcbabb1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "BYQ"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f7e2cd5",
   "metadata": {},
   "source": [
    "### 数列求值"
   ]
  },
  {
   "cell_type": "raw",
   "id": "f223eea1",
   "metadata": {},
   "source": [
    "【问题描述】\n",
    "给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。\n",
    "求第 20190324 项的最后 4 位数字。\n",
    "【答案提交】\n",
    "这是一道结果填空的题，你只需要算出结果后提交即可。\n",
    "本题的结果为一个 4 位整数（提示：答案的千位不为 0），\n",
    "在提交答案时只填写这个整数，填写多余的内容将无法得分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd12a6a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "_1, _2, _3 = 1, 1, 1\n",
    "\n",
    "for i in range(3, 20190324):\n",
    "    \n",
    "    _ = _1 + _2 + _3\n",
    "\n",
    "    _1 = _2\n",
    "\n",
    "    _2 = _3\n",
    "    \n",
    "    _3 = _\n",
    "    \n",
    "print(_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42b9926f",
   "metadata": {},
   "source": [
    "### 数的分解"
   ]
  },
  {
   "cell_type": "raw",
   "id": "4bbf7eb2",
   "metadata": {},
   "source": [
    "把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？\n",
    "\n",
    "   注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。\n",
    "\n",
    "   这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e70dba10",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(2019 // 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71a3c93f",
   "metadata": {},
   "source": [
    "### 特别数的和"
   ]
  },
  {
   "cell_type": "raw",
   "id": "65d14d51",
   "metadata": {},
   "source": [
    "小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），\n",
    "在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，\n",
    "他们的和是 574。 请问，在 1 到 n 中，所有这样的数的和是多少？\n",
    "\n",
    "输入一行包含一个整数 n。\n",
    "\n",
    "输出一行，包含一个整数，表示满足条件的数的和。\n",
    "\n",
    "【样例输入】\n",
    "\n",
    "   40\n",
    "【样例输出】\n",
    "\n",
    "   574\n",
    "\n",
    "对于 20% 的评测用例，1≤n≤10。\n",
    "对于 50% 的评测用例，1≤n≤100。\n",
    "对于 80% 的评测用例，1≤n≤1000。\n",
    "对于所有评测用例，1≤n≤10000。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0f5687e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40\n",
      "574\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "\n",
    "nums = list()\n",
    "for i in range(1, n+1):\n",
    "    string = str(i)\n",
    "    \n",
    "    for char in string:\n",
    "        if char in ['2','0','1','9']:\n",
    "            \n",
    "            nums.append(i)\n",
    "            break\n",
    "\n",
    "print(sum(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61da9e98",
   "metadata": {},
   "source": [
    "### 迷宫"
   ]
  },
  {
   "cell_type": "raw",
   "id": "cd7a3394",
   "metadata": {},
   "source": [
    "下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。\n",
    "010000\n",
    "000100\n",
    "001001\n",
    "110000\n",
    "迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。\n",
    "对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R\n",
    "分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，\n",
    "其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。\n",
    " 请注意在字典序中D<L<R<U。\n",
    " （如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。\n",
    " 在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）\n",
    "\n",
    " 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，\n",
    " 包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填 写多余的内容将无法得分."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "adbb76bb",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "Input \u001b[0;32mIn [1]\u001b[0m, in \u001b[0;36m<cell line: 6>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m x \u001b[38;5;241m!=\u001b[39m \u001b[38;5;241m3\u001b[39m:\n\u001b[1;32m     18\u001b[0m     x \u001b[38;5;241m+\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[0;32m---> 20\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m \u001b[43mpolts\u001b[49m\u001b[43m[\u001b[49m\u001b[43mx\u001b[49m\u001b[43m]\u001b[49m[y] \u001b[38;5;241m==\u001b[39m \u001b[38;5;241m0\u001b[39m:\n\u001b[1;32m     21\u001b[0m         judge\u001b[38;5;241m.\u001b[39mappend(\u001b[38;5;124m'\u001b[39m\u001b[38;5;124mD\u001b[39m\u001b[38;5;124m'\u001b[39m)\n\u001b[1;32m     22\u001b[0m         \u001b[38;5;28;01mcontinue\u001b[39;00m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "polts = [[0,1,0,0,0,0],[0,0,0,1,0,0],[0,0,1,0,0,1],[1,1,0,0,0,0]]\n",
    "\n",
    "x, y = 0, 0\n",
    "\n",
    "judge = list()\n",
    "while x != 3 and y != 5:\n",
    "    \n",
    "    if x != 0:\n",
    "        x -= 1\n",
    "        \n",
    "        if polts[x][y] == 0:\n",
    "            judge.append('U')\n",
    "            continue\n",
    "            \n",
    "        x += 1\n",
    "    \n",
    "    if x != 3:\n",
    "        x += 1\n",
    "        \n",
    "        if polts[x][y] == 0:\n",
    "            judge.append('D')\n",
    "            continue\n",
    "            \n",
    "        x -= 1\n",
    "    \n",
    "    if y != 0:\n",
    "        y -= 1\n",
    "        \n",
    "        if polts[x][y] == 0:\n",
    "            judge.append('L')\n",
    "            continue\n",
    "            \n",
    "        y += 1\n",
    "    \n",
    "    if y != 5:\n",
    "        y += 1\n",
    "        \n",
    "        if polts[x][y] == 0:\n",
    "            judge.append('R')\n",
    "            continue\n",
    "            \n",
    "        y -= 1\n",
    "    \n",
    "    _judge = judge.pop(-1)\n",
    "    \n",
    "    if _judge == 'U':\n",
    "        x += 1\n",
    "        continue\n",
    "        \n",
    "    if _judge == 'D':\n",
    "        x -= 1\n",
    "        continue\n",
    "        \n",
    "    if _judge == 'L':\n",
    "        y += 1\n",
    "        continue\n",
    "    \n",
    "    if _judge == 'R':\n",
    "        y -= 1\n",
    "        continue\n",
    "        \n",
    "print(judge)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f92adbb",
   "metadata": {},
   "source": [
    "### 完全二叉树的和"
   ]
  },
  {
   "cell_type": "raw",
   "id": "d13a0a22",
   "metadata": {},
   "source": [
    "给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，\n",
    "按从上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：\n",
    "\n",
    "现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？\n",
    "如果有多个深度的权值和同为最大，请你输出其中最小的深度。\n",
    "\n",
    "注：根的深度是 1。\n",
    "\n",
    "第一行包含一个整数 N。\n",
    "第二行包含 N 个整数 A1, A2, · · · AN 。\n",
    "\n",
    "输出一个整数代表答案\n",
    "\n",
    "7\n",
    "1 6 5 4 3 2 1\n",
    "\n",
    "2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f260ace7",
   "metadata": {},
   "source": [
    "### 等差数列"
   ]
  },
  {
   "cell_type": "raw",
   "id": "3cfbea0f",
   "metadata": {},
   "source": [
    "试题 H: 等差数列\n",
    "时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分\n",
    "【问题描述】\n",
    "数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一\n",
    "部分的数列，只记得其中 N 个整数。\n",
    "现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有\n",
    "几项？\n",
    "【输入格式】\n",
    "输入的第一行包含一个整数 N。\n",
    "第二行包含 N 个整数 A 1 ,A 2 ,··· ,A N 。(注意 A 1 ∼ A N 并不一定是按等差数\n",
    "列中的顺序给出)\n",
    "【输出格式】\n",
    "输出一个整数表示答案。\n",
    "【样例输入】\n",
    "\n",
    "5\n",
    "2 6 4 10 20\n",
    "【样例输出】\n",
    "10\n",
    "【样例说明】\n",
    "包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、\n",
    "18、20。\n",
    "\n",
    "【评测用例规模与约定】\n",
    "对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ A i ≤ 10^ 9 。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe33e965",
   "metadata": {},
   "source": [
    "### 换钞票"
   ]
  },
  {
   "cell_type": "raw",
   "id": "0d8ca3a8",
   "metadata": {},
   "source": [
    "x星球的钞票的面额只有：100元，5元，2元，1元，共4种。\n",
    "小明去x星旅游，他手里只有2张100元的x星币，太不方便，恰好路过x星银行就去换零钱。\n",
    "小明有点强迫症，他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍，\n",
    "剩下的当然都是5元面额的。\n",
    "\n",
    "银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？\n",
    "（5元，2元，1元面额的必须都有，不能是0）\n",
    "\n",
    "注意，需要提交的是一个整数，不要填写任何多余的内容。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e47ccf7e",
   "metadata": {},
   "source": [
    "### 分数"
   ]
  },
  {
   "cell_type": "raw",
   "id": "4c459104",
   "metadata": {},
   "source": [
    "标题：分数\n",
    "\n",
    "1/1 + 1/2 + 1/4 + 1/8 + 1/16 + …\n",
    "每项是前一项的一半，如果一共有20项,\n",
    "求这个和是多少，结果用分数表示出来。\n",
    "类似：\n",
    "3/2\n",
    "当然，这只是加了前2项而已。分子分母要求互质。\n",
    "\n",
    "注意：\n",
    "需要提交的是已经约分过的分数，中间任何位置不能含有空格。\n",
    "请不要填写任何多余的文字或符号"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lanqiaobei",
   "language": "python",
   "name": "lanqiaobei"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
